Conventionally, a failure location estimate system estimates a path which may be propagating a failure that conforms an output pattern that includes a failure output, and estimating the failure location based on that information.
According to the techniques described in Japanese Laid-Open Patent Application Nos. 08-146093 and 10-062494, a sub-circuit relating to a failure output terminal is extracted to estimate a failure propagation path in the sub-circuit. If necessary, a sub-circuit on the input side is further extracted. Thus, all failure propagation paths are estimated. Then, the weights of the nodes on the paths are calculated based on the connection information of the estimated paths to determine and output nodes with heavier weights in the logic circuit as failure candidates.
Hereinafter, a structure of a conventional technique will be described with reference to the drawings.
FIG. 10 is a block diagram showing an exemplary configuration of a failure propagation path estimate system according to a conventional technique.
Referring to FIG. 10, the system includes an input device 101 which is an interface for a keyboard or other external devices, a failure propagation path estimate processor (or a failure propagation path estimate device or an error propagation path estimate processor) 102 which is operated under the control of a program, a storage device 104 for storing information necessary for a failure propagation path estimate process, and an output device 105 which is an interface for a display device, a printer or other external devices.
The storage device 104 is provided with a logic circuit configuration memory unit 141 and a logic state memory unit 142. The logic circuit configuration memory unit 141 already stores connection relationship among gates and signal lines configuring the logic circuit as well as functions of the gates.
The logic state memory unit 142 stores logic states of individual signal lines subjected to the failure propagation path estimate process as well as logic states (expected values) of the individual signal lines when the circuit is in a normal state.
The failure propagation path estimate device 102 is provided with a failure terminal searching unit 121, a sub-circuit extracting unit 122, a sub-circuit logic state estimating unit 123, a logic state registering unit 124, a failure candidate searching unit 125 and a failure candidate outputting unit 126.
The failure terminal searching unit 121 searches for a failure output terminal by referring to the circuit configuration stored in the logic circuit configuration memory unit 141 and the logic states stored in the logic state memory unit 142. When there is no search target, the failure propagation path estimate process is terminated.
The sub-circuit extracting unit 122 extracts a sub-circuit relating to the failure output terminal searched by the failure terminal searching unit 121 by referring to the circuit configuration stored in the logic circuit configuration memory unit 141.
The sub-circuit logic state estimating unit 123 estimates failure propagation paths within the sub-circuit by referring to the circuit configuration stored in the logic circuit configuration memory unit 141 and the logic states of the boundary of the sub-circuit stored in the logic state memory unit 142.
The logic state registering unit 124 registers the logic states of the sub-circuit estimated by the sub-circuit logic state estimating unit 123 in the logic state memory unit 142.
The failure candidate searching unit 125 searches for, as failure candidates, all nodes (gates, signal lines) on the failure propagation paths which may be propagating a failure state to the failure output, by referring to the failure propagation paths in the sub-circuit estimated by the sub-circuit logic state estimating unit 123.
The failure candidate outputting unit 126 outputs the failure candidates searched by the failure candidate searching unit 125 to the output device 5.
FIG. 11 is an exemplary flowchart of the operation of the system shown in FIG. 10.
The operation according to the conventional technique will be described with reference to FIGS. 10 and 11.
First, the failure terminal searching unit 121 searches for a failure output terminal by referring to the circuit configuration stored in the logic circuit configuration memory unit 141 and the logic states stored in the logic state memory unit 142 (Step A101).
When any search target, i.e., any failure output terminal, is detected, the operation proceeds to Step A103. When no search target is found, the failure propagation path estimate process is terminated (Step A102).
Then, the sub-circuit extracting unit 122 extracts a sub-circuit relating to the failure output terminal searched by the failure terminal searching unit 121 by referring to the circuit configuration stored in the logic circuit configuration memory unit 141 (Step A103). Extraction of the sub-circuit may be carried out by tracing the circuit for a few times in input/output directions or by utilizing the hierarchical design of the circuit as described in Japanese Laid-Open Patent Application No. 10-062494.
Next, the sub-circuit logic state estimating unit 123 estimates failure propagation paths in the sub-circuit by referring to the circuit configuration stored in the logic circuit configuration memory unit 141 as well as the logic states of the boundary of the sub-circuit stored in the logic state memory unit 142 (Step A104).
Then, the logic state registering unit 124 registers the logic states of the sub-circuit estimated in Step A104 in the logic state memory unit 142 (Step A105).
In Step A106, the failure candidate searching unit 125 searches for, as failure candidates, all nodes (gates, signal lines) on the failure propagation paths which may propagate a failure state to the failure output, by referring to the failure propagation paths in the sub-circuit estimated by the sub-circuit logic state estimating unit 123.
The failure candidate outputting unit 126 outputs the failure candidates searched by the failure candidate searching unit 125 to the output device 105 (Step A107).
FIG. 6 is a diagram showing examples of implication operations for 2-input NAND gates in input/output directions.
FIG. 7 is a diagram showing examples of expected values of input/output terminals and logic values of the output signals.
FIG. 8 is a diagram showing an exemplary decision tree for determining logic states.
FIG. 9 is a diagram showing exemplary results of the decision tree.
The flow of operation according to the conventional technique will be described in more detail with reference to FIGS. 6 to 11.
Assume that expected values of the input/output terminals as well as logic values of the output signals (L22=1, L23=1) of target gates are given at an initial state. Then, as can be appreciated from the figure, L23 is the failure output.
The initial state and the expected values of the input/output terminals and the signal lines are as follows: L1=X[1], L2=X[1], L3=X[1], L6=X[1], L7=X[1], L22=1[1] and L23 =1 [0] (numbers in brackets represent the expected values).
In Step A101, the failure terminal searching unit 121 searches the logic circuit for a failure output terminal, whereby L23 is found as the failure terminal.
Since an unprocessed failure terminal is detected, the operation proceeds to Step A103 (Step A102).
In Step A103, a sub-circuit relating to L23 is extracted by the sub-circuit extracting unit 122. Herein, the whole circuit is extracted.
Next, in Step A104, logic states in the sub-circuit are estimated by the sub-circuit logic state estimating unit 123.
Since there is no signal line state implicated by L22=1 and L23=1, signal lines whose logic values are to be assumed are searched. According to Japanese Laid-Open Patent Application No. 11-153646, logic values are assumed for input signal lines of gates which are connected to the failure signal line and whose states have not been confirmed (unconfirmed gate).
Referring to FIG. 6 which shows implication operations for the 2-input NAND gates in input/output directions, when the logic value of an output signal line is [1], either one of the logic values [X] of input signal lines should be [0]. When both of the logic values of the input signal lines are not yet confirmed, the gate is judged as an unconfirmed gate. Here, L16, one of the input signal lines of the gate G23 connected to the failure signal line L23 is assumed to have a logic value [0]. If L16=0, then L2=1 and L11=1 are implicated according to the implication operation for G16.
Thereafter, the implication operation and logic assumption are repeated by assuming logic values for two signal lines, thereby determining three sets of logic states as represented by the decision tree shown in FIG. 8. The determined logic states in the circuit are expressed by logic values of individual signal lines in the order of (L1, L2, L3, L6, L7, L10, L11, L16, L19, L22, L23) within the blocks in FIG. 8. The underlines represent failure propagation paths which differ from the expected values.
Then, in Step A105, the determined logic states in the logic circuit as well as the failure propagation paths are registered in the logic state memory unit 142.
Again, any failure terminal is searched for by the failure terminal searching unit 121 (Step A101). Since there is no unprocessed failure terminal, the operation proceeds to Step A106 (Step A102).
In Step A106, failure candidates on the failure propagation paths are searched for. At this point, three sets of states have been determined. As the failure candidates, {L3, L11, L16, L23} are obtained from a set of states for case1=(X10XX110X11), {L6, L11, L16, L23} are obtained from a set of states for case2=(X110XX10X11), and {L6, L11, L16, L23} are obtained from a set of states for case3=(10101011011). Although L10 is estimated to differ from the expected value, it is neglected since a failure occurring at L10 would not affect L23. L2 in case3 is also neglected for not affecting L23.
These failure candidates are output in Step A107.
Next, a case is assumed where [0] is obtained as a logic state of L11 by measurement of the LSI. According to the conventional technique, the states in the circuit have to be estimated from the failure output terminal again.
L16, one of the input signal lines of the gate G23 connected to the failure signal line L23 is assumed to have a logic value of [0]. If L16=0, then L2=1 and L11=1 are implicated according to the implication operation for G16. However, since an actual measurement value of L11 is obtained as 0, path tracing for L16 ends here.
Next, if L16=1 is assumed, then L10=0 for G22, L19=0 for G23, and L7=1 and L11=1 for G19 are implicated. Since an actual measurement value of L11 is obtained as 0, the estimate process ends due to logic contradiction. Accordingly, a decision tree shown in FIG. 9 is obtained.
Consequently, two sets of logic states are determined. As failure candidates, {L16, L23} are determined from a set of states (XXXXXX00X11) and {L19, L23} are determined from a set of states (XXXXX001011). These failure candidates are output in Step A107.
Next, a case is assumed where [1] is obtained as a logic state of L11 by measurement of the LSI. According to the conventional technique, the states in the circuit have to be estimated from the failure output terminal again.
L16, one of the input signal lines of the gate G23 connected to the failure signal line L23 is assumed to have a logic value of [0]. If L16=0, then L2=1 and L11=1 are implicated according to the implication operation for G16. Since an actual measurement value of L11 is obtained as 1, no contradiction occurs.
By repeating the logic assumption and the implication operation to carry on the estimate process, a decision tree identical to that shown in FIG. 8 is obtained where three sets of logic states are determined. As failure candidates, {L3, L11, L16, L23} are determined from a set of states (X10XX110X11), {L6, L11, L16, L23} are determined from a set of states (X110XX10X11), and {L6, L11, L19, L23} are determined from a set of states (10101011011).
These failure candidates are output in Step A107.
According to the conventional technique, the failure location estimate process has to be repeated from the beginning, meaning that information of a measurement point cannot be fed back to the results of the failure location estimate process. Therefore, the process needs to undergo the same calculation without utilizing the results from the previous estimate process. As a result, the circuit becomes large-scale, and calculation will be enormous when the measurement point is distant from the failure output terminal and deep inside the circuit.
The conventional technique has the following problems.
A first problem is that the failure location estimate process needs to be carried out from the beginning whenever a measurement result is obtained. This is because there is no means for performing the estimate process while adding information of the measurement results to the already estimated results.
A second problem is that the process of re-calculation based on the measurement results takes long time in a large-scale circuit. This is because there is no means for re-calculating only the part relating to the measurement point.
As described above for the operation according to the conventional technique, when information of measurement points is fed back to the results of the failure location estimate process, the failure location estimate process has to be repeated from the beginning. Therefore, the process needs to undergo the same calculation without utilizing the results from the previous estimate process. As a result, the circuit becomes large, and calculation will be enormous when the measurement point is distant from the failure output terminal and deep inside the circuit.